W13. Generative Grammars, Chomsky Hierarchy, and Computability

1. Summary

1.1 Generative Grammars as Language Models

1.1.1 Operational and Generative Viewpoints

In the first half of the course, formal languages were mainly described through operational models such as FSAs, PDAs, and Turing Machines. An operational model receives an input string and decides whether to accept it, reject it, transform it, or compute with it. A grammar gives the complementary perspective: instead of asking whether a string belongs to a language, it explains how strings of the language can be generated.

This distinction is fundamental:

• Automata answer: “Given a string \(w\), is \(w \in L\)?”
• Grammars answer: “What rewriting rules generate exactly the strings in \(L\)?”

In practical computer science, both viewpoints are used together. A grammar specifies a language, while an automaton (or parser) recognises strings of that language. Compiler construction is built on this duality: the grammar defines the syntax of a programming language, and the parser checks whether source code conforms to that syntax.

Two complementary ways to describe a language: recognition by automata and generation by grammars

1.1.2 Computational Linguistics as the Intuition

The grammar idea is easy to understand through natural-language fragments. Suppose we write:

\[\text{(proposition)} \to \text{(noun)(verb)}\] \[\text{(noun)} \to \text{a cat} \mid \text{a dog} \mid \text{a fish}\] \[\text{(verb)} \to \text{meows} \mid \text{barks} \mid \text{swims}\]

Then the grammar can derive strings such as “a dog barks” or “a fish swims”. Symbols like (proposition), (noun), and (verb) are nonterminals: they are placeholders that can still be rewritten. Strings like a dog and swims are terminals: they are final output symbols and are not rewritten further.

This simple linguistic example already contains the central idea of formal grammars: a language is specified by a finite set of replacement rules, and valid sentences are obtained by repeatedly applying those rules until only terminal symbols remain.

1.1.3 Formal Definition of a Grammar

A grammar is a 4-tuple

\[G = \langle V_N, V_T, P, S \rangle\]

where:

• \(V_N\) is the finite set of nonterminal symbols;
• \(V_T\) is the finite set of terminal symbols;
• \(P\) is the finite set of production rules;
• \(S \in V_N\) is the start symbol (also called the axiom).

The alphabets satisfy:

\[V = V_N \cup V_T, \qquad V_N \cap V_T = \emptyset\]

The disjointness condition matters: a symbol cannot be terminal and nonterminal at the same time. The grammar generates strings over \(V_T\), not over the whole mixed alphabet.

1.1.4 Production Rules and Derivations

A production rule is a pair \(\alpha \to \beta\) where:

• \(\alpha \in V^* \cdot V_N \cdot V^*\), so the left-hand side contains at least one nonterminal;
• \(\beta \in V^*\), so the right-hand side may contain terminals, nonterminals, or even be empty.

The condition on the left-hand side is essential. If no nonterminal were required there, rules could rewrite fully terminal strings, which would no longer correspond to “generation by expanding unfinished structure”.

Starting from the axiom \(S\), we repeatedly apply rules:

\[S \Rightarrow \alpha_1 \Rightarrow \alpha_2 \Rightarrow \cdots \Rightarrow w\]

If the final string \(w\) contains only terminal symbols, then \(w\) belongs to the language generated by the grammar. Formally:

\[L(G) = \{w \in V_T^* \mid S \Rightarrow^* w\}\]

The derivation relation \(\Rightarrow^*\) means “in zero or more rewriting steps”. In many examples, this derivation sequence is more informative than a final formula, because it reveals the nested structure that the grammar enforces.

1.1.5 Why Grammars Matter in Programming Languages

Formal grammars are not just theoretical objects. They are the mathematical basis for the syntax of programming languages. In practice, this specification is often written in Backus-Naur Form (BNF) or a close variant. BNF is simply a practical notation for context-free productions, typically written as:

<expr> ::= <expr> + <term> | <term>

The grammar defines what programs look like syntactically. A parser then acts as an automaton that checks whether a token stream fits those productions. This is why the correspondence between grammar classes and automaton classes is so important.

1.2 Chomsky Hierarchy

1.2.1 The Classification Principle

Noam Chomsky classified grammars according to the shape of their productions. The key insight is that the more restrictions we impose on the form of rules, the weaker the grammar becomes and the simpler the corresponding automaton is. This yields the Chomsky hierarchy, a strict nesting of grammar classes and language classes.

Chomsky hierarchy: each weaker grammar class sits strictly inside the stronger ones

The inclusions are proper:

\[\text{Regular} \subsetneq \text{Context-Free} \subsetneq \text{Context-Sensitive} \subsetneq \text{Recursively Enumerable}\]

Each outer class contains languages that the inner class cannot describe.

1.2.2 Type-3: Regular Grammars

A regular grammar is the most restricted grammar class. All productions must be consistently either right-regular or left-regular.

A strictly right-regular grammar allows only productions of the forms:

• \(A \to b\)
• \(A \to bB\)
• \(A \to \epsilon\)

where \(A, B \in V_N\) and \(b \in V_T \cup \{\epsilon\}\).

A strictly left-regular grammar allows only:

• \(A \to b\)
• \(A \to Bb\)
• \(A \to \epsilon\)

The crucial restriction is not merely “at most one nonterminal”, but also that the nonterminal must always stay on the same side of the right-hand side. Mixing left-linear and right-linear rules inside one grammar destroys regularity in general.

Regular grammars generate exactly the regular languages, so they are equivalent in expressive power to Finite State Automata and regular expressions.

1.2.3 Strictly Regular versus Extended Regular Grammars

The tutorials also introduce extended regular grammars. Instead of allowing only a single terminal before or after the optional nonterminal, they allow an entire terminal string:

• right-regular extended form: \(A \to s\) or \(A \to sB\)
• left-regular extended form: \(A \to s\) or \(A \to Bs\)

where \(s \in V_T^*\).

This does not increase expressive power. Any rule like \(A \to a_1 a_2 \cdots a_k B\) can be decomposed into a chain of strict regular rules by introducing helper nonterminals:

\[A \to a_1 A_1,\quad A_1 \to a_2 A_2,\quad \ldots,\quad A_{k-1} \to a_k B\]

So extended regular grammars are merely a more compact notation for the same class of languages.

1.2.4 Type-2: Context-Free Grammars

A context-free grammar (CFG) allows productions of the form:

\[A \to \beta\]

where \(A \in V_N\) and \(\beta \in (V_N \cup V_T)^*\).

This means the left-hand side is a single nonterminal. The rewriting rule for \(A\) is independent of the symbols around it, hence the name context-free. CFGs are powerful enough to describe nested structure such as balanced parentheses, matched blocks, arithmetic expressions, and languages like \(a^n b^n\).

For example, the grammar

\[S \to \epsilon \mid aSb\]

generates exactly the language \(\{a^n b^n \mid n \geq 0\}\). Each time we choose \(aSb\), we add one \(a\) on the left and one \(b\) on the right, so the counts remain equal.

CFGs are precisely the languages recognised by Nondeterministic Pushdown Automata.

1.2.5 Type-1: Context-Sensitive Grammars

A context-sensitive grammar (CSG) has productions that rewrite a nonterminal only in a specified context. A standard form is:

\[\alpha A \beta \to \alpha \gamma \beta\]

where \(\gamma \neq \epsilon\).

The nonterminal \(A\) may be replaced only when surrounded by the context \(\alpha\) and \(\beta\). The condition \(\gamma \neq \epsilon\) makes the grammar non-contracting: it never shortens the sentential form. This monotonicity is a key reason why Type-1 grammars correspond to Linear Bounded Automata (LBAs) rather than arbitrary Turing Machines.

These grammars can express dependencies that are beyond CFG power, such as synchronising three blocks in languages like \(\{a^n b^n c^n \mid n \geq 1\}\).

1.2.6 Type-0: Unrestricted Grammars

At the top of the hierarchy are unrestricted grammars. Their productions have only one real restriction:

\[\alpha \to \beta \qquad \text{with } \alpha \neq \epsilon\]

Aside from forbidding the empty left-hand side, the rule is arbitrary. This class generates the recursively enumerable languages, exactly the languages recognised by Turing Machines.

Thus Type-0 grammars mark the boundary of what can be generated by mechanical computation in the Turing sense.

1.2.7 Summary Table

Chomsky type	Grammar class	Language class	Minimal automaton
Type 0	Unrestricted	Recursively enumerable	Turing Machine
Type 1	Context-sensitive	Context-sensitive	Linear Bounded Automaton
Type 2	Context-free	Context-free	NPDA
Type 3	Regular	Regular	FSA

This table is one of the main maps of the subject. It links grammars, languages, and automata into a single taxonomy.

1.3 Regular Grammars in Detail

1.3.1 Right-Regular and Left-Regular Grammars Recognise the Same Languages

Although right-regular and left-regular productions look different, they generate the same family of languages: the regular languages. Intuitively, a right-regular grammar builds the string from left to right, while a left-regular grammar builds it from right to left. The difference is not expressive power, only orientation.

This is analogous to the equality:

\[\text{Right Regular} = \text{Left Regular} = \text{Regular Languages}\]

1.3.2 Typical Design Pattern of a Regular Grammar

Because regular grammars correspond to FSAs, they are best suited to languages with finite-state memory: local alternation patterns, fixed substrings, parity constraints, and repeated fixed blocks.

Typical constructions use:

• one nonterminal per automaton state;
• productions of the form \(A \to aB\) to follow a labelled transition;
• productions of the form \(A \to \epsilon\) to model an accepting state.

For instance, the grammar

\[S \to \epsilon \mid aB,\qquad B \to bS\]

generates \((ab)^*\), because every trip through \(S \to aB \to abS\) adds one block ab.

1.3.3 Alternation and Embedded Patterns

Regular grammars can enforce simple local structure very efficiently. Examples from the tutorial illustrate this:

• \(\{(ab)^n \mid n \in \mathbb{N}\}\) by cycling between two nonterminals;
• \(\{xaay \mid x, y \in \{a,b\}^*\}\) by scanning arbitrary prefixes, forcing the substring aa, and then scanning arbitrary suffixes;
• alternating symbols by switching between an “a-expected” and a “b-expected” state;
• even-length blocks like \(\{a^{2n} \mid n \in \mathbb{N}\}\) by using a 2-state parity cycle.

These examples are pedagogically important because they reveal how a grammar can be “read as an automaton in disguise”.

1.4 Context-Free Grammars and Pushdown Automata

1.4.1 Why Context-Free Grammars Are More Powerful

Regular grammars cannot count unboundedly. They cannot remember how many \(a\)s were seen in order to compare that number with the number of later \(b\)s. A CFG can encode such matching structure through recursive productions.

The canonical example is:

\[S \to \epsilon \mid aSb\]

Each recursive call postpones the completion of one \(b\) until the right end of the string. This is a form of nested memory, which is exactly what a stack provides computationally.

1.4.2 CFGs and NPDAs Are Equivalent

One of the central facts of formal language theory is:

\[\text{Context-Free Languages} = \text{Languages recognised by NPDAs}\]

The intuition is straightforward.

From CFG to NPDA:

• the stack stores the current unfinished derivation;
• when the top of the stack is a nonterminal, the NPDA non-deterministically applies one of its productions;
• when the top of the stack is a terminal, the NPDA matches it against the next input symbol.

From NPDA to CFG:

• grammar variables are created to describe stack-based transitions between states;
• productions simulate how stack content evolves during a successful computation.

This equivalence explains why grammars and pushdown automata appear together whenever syntax and parsing are studied.

1.4.3 DPDA versus NPDA

The tutorial gives a clean contrast between two languages:

\[L_1 = \{wcw^R \mid w \in \{a,b\}^*\}\] \[L_2 = \{ww^R \mid w \in \{a,b\}^*\}\]

For \(L_1\), the middle marker \(c\) tells the automaton exactly when to switch from the push phase to the pop phase, so a Deterministic PDA (DPDA) is enough.

For \(L_2\), there is no separator. The machine must somehow know where the midpoint lies, but nothing in the next input symbol reveals that. A DPDA cannot do this in general. An NPDA solves the problem by using an \(\epsilon\)-transition to guess the midpoint non-deterministically.

This is one of the most important examples in the course because it shows that, unlike FSAs and Turing Machines, determinism and nondeterminism are not equally powerful for PDAs.

1.4.4 Grammar Perspective on Palindromes

The language of even palindromes can also be described grammatically:

\[S \to \epsilon \mid aSa \mid bSb\]

This rule says: to build a palindrome, choose matching symbols on the left and right, and recursively place another palindrome in the middle. The grammar makes the structural symmetry explicit.

1.4.5 From Grammars to Parsing Notation

The lab agenda explicitly mentions Backus-Naur Form. Conceptually, BNF is not a new language family; it is a notation for context-free syntax rules. Its importance comes from practice rather than expressive novelty. Programming-language syntax is almost always specified in a CFG-like notation because nested structure, precedence, and recursive program forms are naturally context-free.

1.5 Church-Turing Thesis and Effective Computation

1.5.1 The Thesis

The Church-Turing Thesis states that no formal model of mechanical computation is more powerful than a Turing Machine or any equivalent formalism. Equivalently, every effectively calculable algorithm can be computed by a Turing Machine.

This is called a thesis, not a theorem, because it connects a formal mathematical notion (“Turing-computable”) with an intuitive informal notion (“mechanically computable”). The mathematical side can be proved; the equivalence with human intuition cannot be proved in the same purely formal way.

1.5.2 Why the Thesis Is Taken Seriously

The thesis is supported by a very broad convergence phenomenon: many independently developed models of computation turned out to have the same expressive power:

• Turing Machines,
• lambda calculus,
• recursive functions,
• modern high-level programming languages.

Given a Turing Machine, we can write a program that simulates it. Given an ordinary program, we can construct a Turing Machine computing the same function. This is why Turing Machines are treated as the standard formal model of algorithms.

1.5.3 Mechanical Computation and Anthropocentrism

The slides emphasise an important philosophical point: the notion of effective computation is historically tied to what a human mathematician can do step by step with pencil and paper, in finite time, following precise instructions. Turing’s original model idealises this process:

• the tape represents unlimited scratch paper,
• the head represents local reading and writing,
• the finite control represents the current mental state of the procedure.

So the thesis is “universal” only in the mathematical sense: it defines the limits of algorithmic procedure, not the physical limitations of a biological human being.

1.5.4 Static Analysis and Rice’s Theorem

The lecture also motivates decidability through static analysis, the study of program properties without executing the program on all possible inputs. The practical goal is to reason about semantic behaviour, not merely syntax.

The major impossibility result mentioned here is Rice’s theorem: every non-trivial semantic property of the language recognised or function computed by a program is undecidable in full generality. This does not mean static analysis is useless. It means that a perfect, always-terminating, fully precise analyser for arbitrary semantic properties cannot exist. Real tools therefore use approximations, incomplete procedures, or restricted problem classes.

1.6 Gödelization, Universal Turing Machines, and Countability

1.6.1 Enumerating Strings and Turing Machines

The set \(\Sigma^*\) of all finite strings over a finite alphabet is countable. For example, strings over \(\{a,b\}\) can be listed by length and lexicographic order:

\[\epsilon,\ a,\ b,\ aa,\ ab,\ ba,\ bb,\ aaa,\ldots\]

Turing Machines are also countable. Once we fix a finite machine format, each machine can be encoded as a finite description, and finite descriptions can be enumerated. This produces an effective bijection between natural numbers and Turing Machines.

1.6.2 Gödelization

The effective numbering of formal objects by natural numbers is called Gödelization. If \(E\) is the enumeration and \(M\) is a Turing Machine, then \(E(M)\) is the Gödel number of \(M\).

This idea is technically crucial. It lets us talk about “the \(y\)-th Turing Machine” and therefore reason about programs as data.

1.6.3 Universal Turing Machine

Once machines can be encoded as numbers or strings, a single machine can simulate all others. This is the Universal Turing Machine (UTM).

If \(f_y(x)\) denotes the function computed by the \(y\)-th TM on input \(x\), then the UTM computes:

\[g(y, x) = f_y(x)\]

This is the formal origin of the stored-program computer idea:

• ordinary TM: one built-in algorithm,
• UTM: program and data are both supplied as input.

So the UTM is the abstract model of a programmable computer.

1.6.4 Problems versus Programs

Here the course makes a decisive distinction:

• a computational problem is what has to be computed;
• an algorithmic solution is how it is computed.

Mathematically, problems are modelled as functions \(\mathbb{N} \to \mathbb{N}\), while solutions are Turing Machines. This leads to a crucial counting argument:

• Turing Machines are countable, so there are only \(\aleph_0\) algorithms;
• the set of all functions \(\mathbb{N} \to \mathbb{N}\) is much larger.

In particular:

\[|\{f_y : \mathbb{N} \to \mathbb{N}\}| = \aleph_0\]

but

\[|\{f : \mathbb{N} \to \mathbb{N}\}| \ge |\{f : \mathbb{N} \to \{0,1\}\}| = |\wp(\mathbb{N})| = 2^{\aleph_0}\]

Since \(\aleph_0 < 2^{\aleph_0}\), there must exist functions that no Turing Machine computes. Therefore:

there are more computational problems than programs.

Countability gap: algorithms are countable, but all possible problems are uncountable

1.6.5 A Necessary Correction about the Continuum Hypothesis

The raw lecture notes present

\[2^{\aleph_0} = \aleph_1\]

as though it were an established fact. Strictly speaking, this is the Continuum Hypothesis (CH), not a theorem of standard set theory. What is always correct is:

\[|\mathbb{R}| = 2^{\aleph_0}\]

The additional claim that there is no cardinal strictly between \(\aleph_0\) and \(2^{\aleph_0}\) is exactly CH. The pedagogical point needed here does not depend on CH: it is enough that \(2^{\aleph_0}\) is strictly larger than \(\aleph_0\).

1.7 Proof, Diagonalization, and Undecidability

1.7.1 Proof Techniques

The lecture briefly reviews several proof styles:

• direct proof,
• proof by induction,
• constructive proof,
• proof by contradiction,
• proof by diagonalization.

Among these, diagonalization is especially important for computability theory because it constructs an object that necessarily differs from every element of a supposed complete list.

1.7.2 Cantor’s Diagonal Argument

Cantor used diagonalization to show that the real numbers are uncountable. If we assume that all real numbers in \((0,1)\) can be listed, we can build a new real number by changing the first digit of the first number, the second digit of the second number, and so on. The resulting number differs from every listed number in at least one decimal place, so it was not in the list after all. This contradiction proves that no enumeration exists.

The same pattern reappears throughout logic and computability: build an object that escapes every attempt at complete listing.

1.7.3 Russell’s Paradox

The lecture also recalls Russell’s paradox, another diagonal-style contradiction. Let

\[R = \{x \mid x \notin x\}\]

be the set of all sets that are not members of themselves. Then asking whether \(R \in R\) yields:

\[R \in R \iff R \notin R\]

which is impossible. The paradox shows that unrestricted set formation leads to contradiction and motivates axiomatic set theories such as Zermelo-Fraenkel set theory.

1.7.4 Why Diagonalization Matters for Computability

Diagonalization is the conceptual engine behind undecidability proofs such as the Halting Problem. If programs can be enumerated, then one can ask whether there exists a perfect decider for their behaviour. Diagonal arguments show that any such universal decider would fail on a carefully constructed self-referential input.

This is the deep connection among Cantor, Gödel, Russell, and Turing: all of them expose limits of formal systems by constructing an object that cannot fit inside the allegedly complete system.

1.7.5 Decidable, Semi-Decidable, and Undecidable Problems

A problem is:

• decidable if some Turing Machine always halts and correctly answers on every input;
• semi-decidable (recursively enumerable) if some Turing Machine accepts every positive instance, but may loop forever on negative ones;
• undecidable if no Turing Machine decides it.

The course trajectory therefore moves from simple regular languages inside the decidable region to the outer boundary where algorithmic solvability itself breaks down.

---

2. Definitions

• Operational model: A computational model that receives an input string and processes it to accept, reject, translate, or compute.
• Generative model: A model, such as a grammar, that specifies a language by rules that generate its strings.
• Grammar: A 4-tuple \(G = \langle V_N, V_T, P, S \rangle\) consisting of nonterminals, terminals, productions, and a start symbol.
• Nonterminal symbol: A symbol that may still be rewritten by production rules.
• Terminal symbol: A final symbol of the generated language that is not rewritten further.
• Production rule: A rewriting rule \(\alpha \to \beta\) with \(\alpha\) containing at least one nonterminal.
• Axiom / Start symbol: The distinguished nonterminal \(S\) from which derivations begin.
• Derivation: A sequence of rule applications that rewrites the start symbol into a terminal string.
• Language generated by a grammar: The set \(L(G) = \{w \in V_T^* \mid S \Rightarrow^* w\}\).
• BNF (Backus-Naur Form): A practical notation for context-free productions used to specify programming-language syntax.
• Chomsky hierarchy: The four-level classification of grammars into Type 0, Type 1, Type 2, and Type 3.
• Regular grammar: A grammar whose productions are consistently right-regular or left-regular; equivalent to regular languages.
• Strictly right-regular grammar: A regular grammar with productions only of the forms \(A \to b\), \(A \to bB\), or \(A \to \epsilon\).
• Strictly left-regular grammar: A regular grammar with productions only of the forms \(A \to b\), \(A \to Bb\), or \(A \to \epsilon\).
• Extended regular grammar: A compact regular grammar allowing terminal strings in rules such as \(A \to s\) or \(A \to sB\) (or \(A \to Bs\) in the left-linear case).
• Context-free grammar (CFG): A grammar whose productions have a single nonterminal on the left-hand side: \(A \to \beta\).
• Context-sensitive grammar (CSG): A grammar whose productions rewrite a nonterminal only within a specific context and do not contract the sentential form.
• Unrestricted grammar: A Type-0 grammar with productions \(\alpha \to \beta\) where \(\alpha \neq \epsilon\); equivalent to Turing Machines.
• Finite State Automaton (FSA): The automaton model equivalent to regular grammars and regular expressions.
• Deterministic Pushdown Automaton (DPDA): A PDA whose transition relation is single-valued and conflict-free.
• Non-deterministic Pushdown Automaton (NPDA): A PDA that may have multiple valid transitions from one configuration; equivalent to CFGs in expressive power.
• Linear Bounded Automaton (LBA): A Turing Machine restricted to workspace bounded linearly by the input length; equivalent to context-sensitive grammars.
• Church-Turing Thesis: The claim that every effectively calculable algorithm can be computed by a Turing Machine or an equivalent model.
• Effective computability: The intuitive notion of being computable by a finite, mechanical, step-by-step procedure.
• Static analysis: Reasoning about program behaviour without executing the program on all possible inputs.
• Rice’s theorem: The theorem that every non-trivial semantic property of program behaviour is undecidable in full generality.
• Gödelization: The effective encoding of formal objects such as Turing Machines by natural numbers.
• Gödel number: The number assigned to a formal object under a Gödelization.
• Universal Turing Machine (UTM): A Turing Machine that simulates any other Turing Machine given its encoding and its input.
• Countable set: A set that can be put into bijection with \(\mathbb{N}\).
• Uncountable set: A set that cannot be enumerated by natural numbers.
• Continuum Hypothesis (CH): The statement that no cardinality lies strictly between \(\aleph_0\) and \(2^{\aleph_0}\), equivalently \(2^{\aleph_0} = \aleph_1\).
• Diagonalization: A proof technique that constructs an object differing from every member of a purported complete list.
• Russell’s paradox: The contradiction obtained from considering the set of all sets that are not members of themselves.
• Decidable problem: A problem for which some Turing Machine always halts with the correct yes/no answer.
• Semi-decidable problem: A problem for which some Turing Machine accepts all yes-instances but may not halt on no-instances.
• Undecidable problem: A problem for which no Turing Machine can decide every input correctly.

---

3. Formulas

• Grammar tuple: \(G = \langle V_N, V_T, P, S \rangle\)
• Alphabet decomposition: \(V = V_N \cup V_T,\quad V_N \cap V_T = \emptyset\)
• Production-rule domain: \(P \subseteq (V^* \cdot V_N \cdot V^*) \times V^*\)
• Generated language: \(L(G) = \{w \in V_T^* \mid S \Rightarrow^* w\}\)
• Context-free production form: \(A \to \beta\)
• Context-sensitive production form: \(\alpha A \beta \to \alpha \gamma \beta,\quad \gamma \neq \epsilon\)
• Unrestricted production form: \(\alpha \to \beta,\quad \alpha \neq \epsilon\)
• Strict hierarchy: \(\text{Regular} \subsetneq \text{Context-Free} \subsetneq \text{Context-Sensitive} \subsetneq \text{Recursively Enumerable}\)
• Universal TM function: \(g(y, x) = f_y(x)\)
• Countability of algorithms: \(|\{f_y : \mathbb{N} \to \mathbb{N}\}| = \aleph_0\)
• Lower bound on all problems: \(|\{f : \mathbb{N} \to \mathbb{N}\}| \ge |\{f : \mathbb{N} \to \{0,1\}\}| = |\wp(\mathbb{N})| = 2^{\aleph_0}\)
• Cardinality of the reals: \(|\mathbb{R}| = 2^{\aleph_0}\)
• Continuum Hypothesis: \(2^{\aleph_0} = \aleph_1\)
• Russell paradox statement: \(R = \{x \mid x \notin x\}\) and hence \(R \in R \iff R \notin R\)

---

4. Examples

4.1. Generate Alternating Strings with a Regular Grammar (Lab 12, Example 1)

Construct a regular grammar that generates strings over \(\{a, b\}\) in which the symbols alternate.

Click to see the solution

Key Concept: A regular grammar can enforce alternation by using different nonterminals for the two possible next symbols.

The source grammar is:

\[S \to A \mid B,\qquad A \to aB \mid \epsilon,\qquad B \to bA \mid \epsilon\]

Step 1. Interpret the nonterminals.

• \(A\) means: the next symbol, if any, must be a.
• \(B\) means: the next symbol, if any, must be b.
• \(S\) chooses whether the string starts with a or b.

Step 2. See why alternation is enforced.

If we are in \(A\), the only non-empty production is \(A \to aB\), so after emitting a we must move to \(B\). Similarly, from \(B\) the only non-empty production is \(B \to bA\), so after emitting b we must move back to \(A\). This alternation is built into the grammar itself.

Step 3. Check sample derivations.

For aba:

\[S \Rightarrow A \Rightarrow aB \Rightarrow abA \Rightarrow aba\]

For baba:

\[S \Rightarrow B \Rightarrow bA \Rightarrow baB \Rightarrow babA \Rightarrow baba\]

Answer: A correct regular grammar is \(S \to A \mid B\), \(A \to aB \mid \epsilon\), \(B \to bA \mid \epsilon\), and it generates exactly the alternating strings over \(\{a,b\}\), including \(\epsilon\).

4.2. Generate \(a^n b^n\) with a Context-Free Grammar (Lab 12, Example 2)

Construct a context-free grammar for the language \(L = \{a^n b^n \mid n > 0\}\).

Click to see the solution

Key Concept: A CFG for \(a^n b^n\) works by adding one matching a and b at each recursive step and stopping at a nonempty base case.

A standard grammar is:

\[S \to aSb \mid ab\]

Why this works.

Every time we apply \(S \to aSb\), we add one a on the left and one b on the right. Therefore the grammar always preserves equality between the number of as and bs.

The production \(S \to ab\) is the base case. It ensures that the smallest generated string is ab, so \(n > 0\).

Example derivations.

For \(n = 1\):

\[S \Rightarrow ab\]

For \(n = 2\):

\[S \Rightarrow aSb \Rightarrow a(ab)b = aabb\]

For \(n = 3\):

\[S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aa(ab)bb = aaabbb\]

Answer: A standard CFG is \(S \to aSb \mid ab\), and it generates exactly the language \(\{a^n b^n \mid n > 0\}\).

4.3. Construct a Strictly Regular Grammar for \((aa \mid bb)^*aa\) (Lab 12, Task 1)

Define a strictly regular grammar for the language \(L = (aa \mid bb)^*aa\).

Click to see the solution

Key Concept: A strictly regular grammar for repeated fixed-size blocks uses helper nonterminals to remember partial progress inside each block.

An effective strictly right-regular grammar is:

\[S \to aA \mid bB,\qquad A \to aS \mid a,\qquad B \to bS\]

Step 1. Understand the target language.

Strings are built from blocks aa and bb, but the final block must be aa. So examples are:

\[aa,\quad aaaa,\quad bbaa,\quad aabbaa,\quad bbbbaa,\ \ldots\]

Step 2. Interpret the grammar states.

• \(S\) means “we are at the start of a new 2-letter block”.
• \(A\) means “we already wrote the first a of an aa block”.
• \(B\) means “we already wrote the first b of a bb block”.

Step 3. Check the productions.

• \(S \to aA\) starts an aa block.
• \(S \to bB\) starts a bb block.
• \(B \to bS\) completes the bb block and returns to the block-start state.
• \(A \to aS\) completes an internal aa block and allows more blocks.
• \(A \to a\) completes the final aa block and stops.

Step 4. Verify with derivations.

For aa:

\[S \Rightarrow aA \Rightarrow aa\]

For bbaa:

\[S \Rightarrow bB \Rightarrow bbS \Rightarrow bbaA \Rightarrow bbaa\]

For aaa a:

\[S \Rightarrow aA \Rightarrow aaS \Rightarrow aaaA \Rightarrow aaaa\]

This is valid because aaaa = aa \cdot aa.

Answer: One strictly regular grammar is \(S \to aA \mid bB\), \(A \to aS \mid a\), \(B \to bS\), and it generates exactly \((aa \mid bb)^*aa\).

4.4. Construct a Strictly Regular Grammar for \(00^*11^*\) (Lab 12, Task 2)

Define a strictly regular grammar for the language \(L = 00^*11^*\), that is, one or more 0s followed by one or more 1s.

Click to see the solution

Key Concept: The grammar needs one phase for one-or-more 0s and one later phase for one-or-more 1s, with no transition back to the zero phase.

A simple strictly right-regular grammar is:

\[S \to 0S \mid 0A,\qquad A \to 1A \mid 1\]

Step 1. Interpret the two phases.

• State \(S\) generates the block of 0s.
• State \(A\) generates the block of 1s.

The grammar allows the switch from 0-phase to 1-phase exactly once.

Step 2. Check the meaning of each rule.

• \(S \to 0S\) adds another 0 and stays in the 0-phase.
• \(S \to 0A\) emits the final 0 and enters the 1-phase.
• \(A \to 1A\) adds another 1.
• \(A \to 1\) emits the final 1 and terminates.

Step 3. Verify examples.

For 01:

\[S \Rightarrow 0A \Rightarrow 01\]

For 000111:

\[S \Rightarrow 0S \Rightarrow 00S \Rightarrow 000A \Rightarrow 0001A \Rightarrow 00011A \Rightarrow 000111\]

Why no invalid string is generated.

The grammar never returns from \(A\) to \(S\), so once a 1 is produced, no later 0 can appear. Also, there is no \(\epsilon\)-production, so at least one 0 and one 1 are mandatory.

Answer: A correct strictly regular grammar is \(S \to 0S \mid 0A\), \(A \to 1A \mid 1\), which generates exactly \(00^*11^*\).

4.5. Construct a CFG for Alternating \(a\)’s and \(b\)’s (Lab 12, Task 3)

Define a context-free grammar for the language of alternating a and b symbols.

Click to see the solution

Key Concept: Even though alternating strings form a regular language, a CFG can still describe them by storing which opposite symbol must come next.

One convenient CFG is:

\[S \to \epsilon \mid aA \mid bB,\qquad A \to \epsilon \mid bS,\qquad B \to \epsilon \mid aS\]

Step 1. Interpret the grammar.

• \(S\) chooses whether the next symbol starts with a, starts with b, or the string is empty.
• \(A\) means: after an a, we may stop or we must place b.
• \(B\) means: after a b, we may stop or we must place a.

Step 2. Check typical derivations.

For ab:

\[S \Rightarrow aA \Rightarrow abS \Rightarrow ab\]

For baba:

\[S \Rightarrow bB \Rightarrow baS \Rightarrow babB \Rightarrow babaS \Rightarrow baba\]

For a:

\[S \Rightarrow aA \Rightarrow a\]

Step 3. Explain correctness.

The grammar alternates because:

• from \(A\), only b can follow;
• from \(B\), only a can follow.

No rule can generate two consecutive equal symbols.

Answer: A suitable CFG is \(S \to \epsilon \mid aA \mid bB\), \(A \to \epsilon \mid bS\), \(B \to \epsilon \mid aS\), and it generates exactly the alternating strings.

4.6. Construct a CFG for \(\{a^n b^n c^m\} \cup \{a^n b^m c^m\}\) (Lab 12, Task 4)

Define a context-free grammar for

\[L = \{a^n b^n c^m \mid n, m > 0\} \cup \{a^n b^m c^m \mid n, m > 0\}.\]

Click to see the solution

Key Concept: For a union of two structured languages, the cleanest CFG usually splits the start symbol into one branch per sublanguage.

Use the union decomposition:

\[L = L_1 \cup L_2\]

where

\[L_1 = \{a^n b^n c^m \mid n, m > 0\},\qquad L_2 = \{a^n b^m c^m \mid n, m > 0\}.\]

A CFG is:

\[S \to X \mid Y\] \[X \to AC,\qquad A \to aAb \mid ab,\qquad C \to cC \mid c\] \[Y \to aY \mid aB,\qquad B \to bBc \mid bc\]

Step 1. Verify the \(L_1\) branch.

The nonterminal \(A\) generates \(a^n b^n\) with \(n > 0\), and \(C\) generates \(c^m\) with \(m > 0\). Therefore \(X \to AC\) generates:

\[a^n b^n c^m \qquad (n,m > 0)\]

Step 2. Verify the \(L_2\) branch.

The nonterminal \(Y\) first creates at least one leading a. Then \(B\) generates \(b^m c^m\) with \(m > 0\). Hence the \(Y\) branch generates:

\[a^n b^m c^m \qquad (n,m > 0)\]

Step 3. Sample derivations.

For aabbc in \(L_1\):

\[S \Rightarrow X \Rightarrow AC \Rightarrow aAbbC \Rightarrow aabbC \Rightarrow aabbc\]

For aaabbbccc in \(L_2\):

\[S \Rightarrow Y \Rightarrow aY \Rightarrow aaY \Rightarrow aaaB \Rightarrow aaabB c \Rightarrow aaabbBcc \Rightarrow aaabbbccc\]

Answer: A correct CFG is \(S \to X \mid Y\), \(X \to AC\), \(A \to aAb \mid ab\), \(C \to cC \mid c\), \(Y \to aY \mid aB\), \(B \to bBc \mid bc\), which generates \(\{a^n b^n c^m\} \cup \{a^n b^m c^m\}\) for positive indices.

4.7. Construct a Strictly Regular Grammar for \(\{0,1\}^*\) (Lab 12, Task 5)

Define a strictly regular grammar for all binary strings.

Click to see the solution

Key Concept: For \(\{0,1\}^*\), one nonterminal with loops on both terminals and an \(\epsilon\) stop rule is sufficient.

A minimal grammar is:

\[S \to 0S \mid 1S \mid \epsilon\]

Why this works.

At each step:

• choose \(0S\) to append a 0,
• choose \(1S\) to append a 1,
• choose \(\epsilon\) to stop.

Because these choices are available at every stage, the grammar generates every finite binary string and only binary strings.

Examples.

For 1010:

\[S \Rightarrow 1S \Rightarrow 10S \Rightarrow 101S \Rightarrow 1010S \Rightarrow 1010\]

For \(\epsilon\):

\[S \Rightarrow \epsilon\]

This is the standard regular grammar corresponding to a one-state accepting automaton with self-loops on 0 and 1.

Answer: A minimal strictly regular grammar is \(S \to 0S \mid 1S \mid \epsilon\), and it generates every binary string and only binary strings.

4.8. Construct a Strictly Regular Grammar for \((aab \mid bba)^*\) (Lab 12, Task 6)

Define a strictly regular grammar for

\[L = (aab \mid bba)^*.\]

Click to see the solution

Key Concept: A regular grammar for a repeated fixed-block language should return to the start state only after completing one full allowed block.

One strictly right-regular grammar is:

\[S \to \epsilon \mid aA \mid bD\] \[A \to aB,\qquad B \to bS\] \[D \to bE,\qquad E \to aS\]

Step 1. Separate the two allowed blocks.

The language consists of repeated copies of either:

• aab, or
• bba.

So from \(S\) we either stop, start the aab branch, or start the bba branch.

Step 2. Follow the branches.

• \(S \to aA \to aaB \to aabS\) generates one aab block.
• \(S \to bD \to bbE \to bbaS\) generates one bba block.

Returning to \(S\) after each full block allows repetition.

Step 3. Verify examples.

For aabb a:

\[S \Rightarrow aA \Rightarrow aaB \Rightarrow aabS \Rightarrow aab bD \Rightarrow aabbbE \Rightarrow aabbbaS \Rightarrow aabbba\]

This is aab followed by bba, so it belongs to the language.

Answer: One strictly regular grammar is \(S \to \epsilon \mid aA \mid bD\), \(A \to aB\), \(B \to bS\), \(D \to bE\), \(E \to aS\), and it generates exactly \((aab \mid bba)^*\).

4.9. Construct a CFG for Palindromes over \(\{a,b\}\) (Lab 12, Task 7)

Define a context-free grammar for

\[L = \{w \in \{a,b\}^* \mid w = w^R\}.\]

Click to see the solution

Key Concept: A palindrome grammar adds matching symbols on both ends and recurses on a smaller palindrome in the middle.

A classical grammar is:

\[S \to aSa \mid bSb \mid a \mid b \mid \epsilon\]

Step 1. Understand the recursive idea.

To make a palindrome:

• choose matching symbols on both ends;
• place a smaller palindrome in the middle.

That is exactly what \(aSa\) and \(bSb\) do.

Step 2. Explain the base cases.

• \(\epsilon\) gives the empty palindrome;
• \(a\) and \(b\) give the odd-length palindromes of length 1.

So the grammar covers both even and odd palindromes.

Step 3. Sample derivations.

For abba:

\[S \Rightarrow aSa \Rightarrow abSba \Rightarrow ab\epsilon ba = abba\]

For bab:

\[S \Rightarrow bSb \Rightarrow bab\]

Why this is context-free.

Each production rewrites a single nonterminal \(S\), regardless of context. The symmetry of the string is encoded by recursion, not by context-sensitive side conditions.

Answer: A standard CFG is \(S \to aSa \mid bSb \mid a \mid b \mid \epsilon\), and it generates exactly the palindromes over \(\{a,b\}\).

4.10. Construct a CFG for \(a^i b^j c^k\) with \(i=j\) or \(i=k\) (Lab 12, Task 8)

Define a context-free grammar for

\[L = \{a^i b^j c^k \mid i,j,k \ge 0 \text{ and } (i=j \text{ or } i=k)\}.\]

Click to see the solution

Key Concept: The condition “\(i=j\) or \(i=k\)” is naturally modeled as a union of two context-free branches, one for each equality.

Split the language into two context-free parts:

\[L = L_1 \cup L_2\]

where

\[L_1 = \{a^i b^i c^k \mid i,k \ge 0\},\qquad L_2 = \{a^i b^j c^i \mid i,j \ge 0\}.\]

A CFG is:

\[S \to X \mid Y\] \[X \to AC,\qquad A \to aAb \mid \epsilon,\qquad C \to cC \mid \epsilon\] \[Y \to aYc \mid B,\qquad B \to bB \mid \epsilon\]

Step 1. Check the \(X\) branch.

The nonterminal \(A\) produces equal numbers of as and bs. The nonterminal \(C\) then appends any number of cs. So \(X\) generates exactly \(a^i b^i c^k\).

Step 2. Check the \(Y\) branch.

Each use of \(aYc\) adds one a to the front and one c to the back, preserving equality between the number of as and cs. The middle nonterminal \(B\) then inserts any number of bs. Thus \(Y\) generates exactly \(a^i b^j c^i\).

Step 3. Sample derivations.

For aabbccc with \(i=j=2\):

\[S \Rightarrow X \Rightarrow AC \Rightarrow aAbC \Rightarrow aaAbbC \Rightarrow aabbC \Rightarrow aabbcC \Rightarrow aabbccC \Rightarrow aabbccc\]

For abbbc with \(i=k=1\):

\[S \Rightarrow Y \Rightarrow aYc \Rightarrow aBc \Rightarrow abBc \Rightarrow abbBc \Rightarrow abbbBc \Rightarrow abbbc\]

Answer: A correct CFG is \(S \to X \mid Y\), \(X \to AC\), \(A \to aAb \mid \epsilon\), \(C \to cC \mid \epsilon\), \(Y \to aYc \mid B\), \(B \to bB \mid \epsilon\), which generates exactly the strings with \(i=j\) or \(i=k\).

4.11. Generate \((ab)^n\) with a Right-Regular Grammar (Tutorial 12, Example 1)

Construct a right-regular grammar for

\[L = \{(ab)^n \mid n \in \mathbb{N}\}.\]

Click to see the solution

Key Concept: The cycle \(S \Rightarrow aB \Rightarrow abS\) adds exactly one full ab block per iteration, while \(\epsilon\) stops the derivation.

A standard grammar is:

\[S \to \epsilon \mid aB,\qquad B \to bS\]

Step 1. Understand the cycle.

The path

\[S \Rightarrow aB \Rightarrow abS\]

adds one full block ab.

Step 2. Explain the base case.

The rule \(S \to \epsilon\) allows the derivation to stop after any number of full ab blocks, including zero. Therefore \(\epsilon\) belongs to the language, which matches the convention \(n \in \mathbb{N}\) with \(n = 0\) allowed.

Step 3. Sample derivations.

For ab:

\[S \Rightarrow aB \Rightarrow abS \Rightarrow ab\]

For abab:

\[S \Rightarrow aB \Rightarrow abS \Rightarrow abaB \Rightarrow ababS \Rightarrow abab\]

Automaton view of the grammar for (ab)*

Answer: A right-regular grammar for \((ab)^*\) is \(S \to \epsilon \mid aB\), \(B \to bS\).

4.12. Generate Strings Containing the Substring aa (Tutorial 12, Example 2)

Construct a right-regular grammar for

\[L = \{xaay \mid x, y \in \{a,b\}^*\}.\]

Click to see the solution

Key Concept: To force a required substring inside an arbitrary string, use one phase for the free prefix, one forced transition for the substring, and one phase for the free suffix.

One grammar is:

\[S \to aS \mid bS \mid aA,\qquad A \to aB,\qquad B \to aB \mid bB \mid \epsilon\]

Step 1. Interpret the three stages.

• \(S\) generates an arbitrary prefix \(x\) over \(\{a,b\}^*\).
• The transition \(S \to aA \to aaB\) forces the substring aa.
• \(B\) generates an arbitrary suffix \(y\) over \(\{a,b\}^*\).

Step 2. Explain why every generated string contains aa.

The only way to terminate is through \(B \Rightarrow^* y\), and reaching \(B\) requires the sequence \(S \to aA \to aaB\). So every derivation necessarily contains the substring aa.

Step 3. Explain why every string of the form \(xaay\) is generated.

Use the loop rules \(S \to aS\) and \(S \to bS\) to generate the desired prefix \(x\), then use \(S \to aA \to aaB\) for the required middle substring, and finally use \(B \to aB \mid bB \mid \epsilon\) to generate the suffix \(y\).

Three-state automaton for the language x a a y

Answer: An appropriate right-regular grammar is \(S \to aS \mid bS \mid aA\), \(A \to aB\), \(B \to aB \mid bB \mid \epsilon\), which generates exactly all strings containing the substring aa.

4.13. Generate \(a^{2n}\) with a Regular Grammar (Tutorial 12, Example 3)

Construct a regular grammar for

\[L = \{a^{2n} \mid n \in \mathbb{N}\}.\]

Click to see the solution

Key Concept: The only productive cycle adds two as at a time, so every derived nonempty string has even length.

A compact grammar is:

\[S \to aA \mid \epsilon,\qquad A \to aS\]

Why this works.

The only way to emit symbols is through the cycle

\[S \Rightarrow aA \Rightarrow aaS\]

which adds exactly two as at a time. The rule \(S \to \epsilon\) ends the derivation after any number of such cycles.

Sample derivations.

For aa:

\[S \Rightarrow aA \Rightarrow aaS \Rightarrow aa\]

For aaaa:

\[S \Rightarrow aA \Rightarrow aaS \Rightarrow aaaA \Rightarrow aaaaS \Rightarrow aaaa\]

The tutorial also asks whether one can write simply

\[S \to aaS \mid \epsilon\]

Yes: this is an extended right-regular grammar. It is equivalent in expressive power to the strict version above.

Answer: A strict regular grammar is \(S \to aA \mid \epsilon\), \(A \to aS\); equivalently, the extended rule form is \(S \to aaS \mid \epsilon\).

4.14. Convert the Grammar for \((ab)^n\) into Extended Regular Form (Tutorial 12, Example 4)

Rewrite the strict grammar for \((ab)^*\) in extended regular form.

Click to see the solution

Key Concept: An extended regular rule compresses a fixed multi-step strict derivation into one shorthand production.

The strict grammar was:

\[S \to \epsilon \mid aB,\qquad B \to bS\]

The two-step chain

\[S \Rightarrow aB \Rightarrow abS\]

behaves exactly like a single extended rule:

\[S \to abS\]

So the equivalent extended grammar is:

\[S \to abS \mid \epsilon\]

Why this is valid.

Extended regular rules are just shorthand. The rule \(S \to abS\) can always be decomposed back into strict form by introducing a helper nonterminal:

\[S \to aB,\qquad B \to bS\]

So the two grammars are equivalent, and the second is simply more compact.

Answer: The extended regular form is \(S \to abS \mid \epsilon\).

4.15. Convert the Grammar for \(xaay\) into Extended Regular Form (Tutorial 12, Example 5)

Rewrite the strict grammar for \(L = \{xaay \mid x, y \in \{a,b\}^*\}\) in extended regular form.

Click to see the solution

Key Concept: Extended regular form merges the forced two-step chain that inserts aa into one direct production.

The strict grammar was:

\[S \to aS \mid bS \mid aA,\qquad A \to aB,\qquad B \to aB \mid bB \mid \epsilon\]

The chain

\[S \Rightarrow aA \Rightarrow aaB\]

can be compressed into the extended rule \(S \to aaB\). Therefore the equivalent extended grammar is:

\[S \to aS \mid bS \mid aaB,\qquad B \to aB \mid bB \mid \epsilon\]

The meaning is unchanged:

• the first two rules generate the prefix \(x\),
• the extended rule inserts the required substring aa,
• the \(B\) rules generate the suffix \(y\).

Answer: The extended regular grammar is \(S \to aS \mid bS \mid aaB\), \(B \to aB \mid bB \mid \epsilon\).

4.16. Construct a DPDA for \(wcw^R\) (Tutorial 12, Example 6)

Construct a deterministic PDA for

\[L = \{wcw^R \mid w \in \{a,b\}^*\}.\]

Click to see the solution

Key Concept: The separator c tells the machine exactly when the first half ends.

Use three states:

• \(q_0\): push phase,
• \(q_1\): pop/match phase,
• \(q_2\): accepting state.

Push phase transitions in \(q_0\).

For each input symbol before c, push a matching stack marker:

• on a, push \(A\);
• on b, push \(B\).

Formally:

• \(a, Z_0 / AZ_0\), \(a, A / AA\), \(a, B / AB\)
• \(b, Z_0 / BZ_0\), \(b, A / BA\), \(b, B / BB\)

Switch transition.

When the machine reads c, it moves to \(q_1\) without changing the top stack symbol:

• \(c, Z_0 / Z_0\)
• \(c, A / A\)
• \(c, B / B\)

Pop phase transitions in \(q_1\).

• \(a, A / \epsilon\)
• \(b, B / \epsilon\)

Acceptance.

When the input is finished and only \(Z_0\) remains, move to \(q_2\):

• \(\epsilon, Z_0 / Z_0\)

The machine is deterministic because the symbol c provides an unambiguous switching point.

DPDA for wcw^R: separator c marks the midpoint deterministically

Answer: A DPDA for \(wcw^R\) uses one push phase before reading c, one deterministic pop phase after c, and accepts when the input ends exactly as the stack returns to its bottom marker.

4.17. Construct an NPDA for \(ww^R\) (Tutorial 12, Example 7)

Construct a nondeterministic PDA for

\[L = \{ww^R \mid w \in \{a,b\}^*\}.\]

Click to see the solution

Key Concept: Without a separator, the PDA must guess the midpoint nondeterministically, because no deterministic signal marks where the second half begins.

Here there is no separator, so the machine must guess the midpoint.

Use the same three logical states:

• \(q_0\): push phase,
• \(q_1\): pop/match phase,
• \(q_2\): accepting state.

Push phase.

Exactly as before, on each a push \(A\), and on each b push \(B\).

Non-deterministic midpoint guess.

From \(q_0\) the machine may move to \(q_1\) by an \(\epsilon\)-transition at any time:

• \(\epsilon, Z_0 / Z_0\)
• \(\epsilon, A / A\)
• \(\epsilon, B / B\)

This does not consume input and does not change the stack. It only switches interpretation from “first half” to “second half”.

Pop phase.

• \(a, A / \epsilon\)
• \(b, B / \epsilon\)

Acceptance.

Accept when the input is exhausted and the stack has returned to \(Z_0\).

The machine works because one branch of the nondeterministic computation guesses the true midpoint. Branches that guess too early or too late eventually fail to match and reject.

NPDA for ww^R: ε-transition guesses where the second half starts

Why no DPDA can do the same.

A DPDA has no information telling it where the midpoint is. If it switches from push to pop too early or too late, there is no second chance. Nondeterminism is essential.

Answer: An NPDA for \(ww^R\) uses an \(\epsilon\)-transition to guess when to switch from pushing to popping; that midpoint guess is exactly why an NPDA works and a DPDA does not.

4.18. Generate \(ww^R\) with a Context-Free Grammar (Tutorial 12, Example 8)

Construct a grammar for

\[L = \{ww^R \mid w \in \{a,b\}^*\}.\]

Click to see the solution

Key Concept: The language \(ww^R\) is exactly the set of even palindromes, so the grammar just adds matching symbols around a smaller symmetric core.

The grammar is:

\[S \to \epsilon \mid aSa \mid bSb\]

This is the even-palindrome grammar already seen in the lab exercises.

Why it matches \(ww^R\).

Every derived string is symmetric: each recursion step adds the same symbol on the left and on the right. Conversely, every even palindrome can be reduced by stripping matching outer symbols until the empty string is reached.

Example derivation.

For abbbba:

\[S \Rightarrow aSa \Rightarrow abSba \Rightarrow abbSbba \Rightarrow abbbSbbba \Rightarrow abbbba\]

The middle eventually disappears via \(S \to \epsilon\), so the total length is even.

Answer: A CFG for \(ww^R\) is \(S \to \epsilon \mid aSa \mid bSb\).

4.19. Convert the Grammar \(S \to \epsilon \mid aSb\) into an NPDA (Tutorial 12, Example 9)

Construct an NPDA corresponding to the grammar

\[S \to \epsilon \mid aSb.\]

Click to see the solution

Key Concept: The PDA mirrors the recursive rule \(aSb\) by pushing once for each leading a and popping once for each trailing b.

This grammar generates \(\{a^n b^n \mid n \ge 0\}\). The equivalent PDA has a natural two-phase interpretation.

State idea.

• In the first state, read as and push one marker per a.
• After the switch, read bs and pop one marker per b.

Use states \(q_0\) (push), \(q_1\) (pop), and \(q_F\) (accept).

Transitions.

Push phase:

• \(a, Z_0 / BZ_0\)
• \(a, B / BB\)

Switch to pop phase:

• \(\epsilon, Z_0 / Z_0\)
• \(\epsilon, B / B\)

Pop phase:

• \(b, B / \epsilon\)

Acceptance:

• \(\epsilon, Z_0 / Z_0\)

This construction mirrors the recursive production:

• each application of \(aSb\) corresponds to pushing one marker for the future b,
• the base case \(\epsilon\) corresponds to eventually stopping recursion and beginning the matching phase.

NPDA corresponding to the grammar S → ε | aSb

Answer: The equivalent NPDA has a push phase for as, an \(\epsilon\)-switch to a pop phase for bs, and accepts when the stack returns to the bottom marker exactly at the end of input.

4.20. Construct a PDA for \((abc)^n(ca)^n\) (Tutorial 12, Example 10)

Construct a PDA for

\[L = \{(abc)^n (ca)^n \mid n \in \mathbb{N}\}.\]

Click to see the solution

Key Concept: Each prefix block abc creates one future obligation to match a suffix block ca, so the PDA stores those obligations on the stack.

The tutorial gives the grammar:

\[S \to \epsilon \mid abcSca\]

This means that every time we generate one leading block abc, we also promise one trailing block ca. A PDA should therefore remember, for each abc block, that one future ca block must be matched.

Construction idea.

Use two phases.

1. Prefix phase: read blocks abc. Every completed abc block pushes two markers, say C then A, to remember one future ca.
2. Suffix phase: read blocks ca. On c, pop C; on a, pop A.

State structure.

• \(q_0, q_1, q_2\): recognise one abc block,
• \(q_3\): end of an abc block and possible phase switch,
• \(q_4, q_5\): recognise one ca block,
• \(q_F\): accepting state.

How one abc block is processed.

• \(q_0 \xrightarrow{a} q_1\)
• \(q_1 \xrightarrow{b} q_2\)
• \(q_2 \xrightarrow{c,\ \text{push } CA} q_3\)

From \(q_3\), either:

• return to \(q_0\) to read another abc block, or
• switch to the suffix phase if the next part begins with c.

How one ca block is processed.

• read c and pop C,
• read a and pop A,
• repeat until the stack returns to \(Z_0\).

Why this works.

Each prefix block deposits exactly one pair of obligations (c,a) onto the stack. Each suffix block discharges exactly one such obligation. Therefore the number of abc blocks must equal the number of ca blocks.

The empty string is accepted through the \(n=0\) case.

Answer: A correct PDA reads each abc block in a prefix phase while pushing one CA obligation, then reads each ca block in a suffix phase while popping C and A, so exactly the strings \((abc)^n(ca)^n\) are accepted.